package com.sort;

import java.lang.reflect.Array;
import java.util.*;

public class Solution {
    public static void main(String[] args) {
        BubbleSort bubbleTest = new BubbleSort();
        SelectionSort selectionTest = new SelectionSort();
        QuickSort quickSortTest = new QuickSort();

        // 测试数据
        int[] arr = gennerateArray(20, 100);

        System.out.println("待排序的数组：" + Arrays.toString(arr));

        // bubbleTest.sort02(arr);
        // selectionTest.sort1(arr);
        quickSortTest.sort(arr, 0, arr.length - 1);


        System.out.println("排序结果：" + Arrays.toString(arr));
    }

    // 随机生成数组
    public static int[] gennerateArray(int len, int max) {
        int[] arr = new int[len];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * max);
        }
        return arr;
    }
}


class BubbleSort {

    public void sort(int[] arr) {
        int len = arr.length;
        if (len == 0)
            return;

        //  循环n次
        for (int end = len - 1; end > 0; end--) {
            for (int begin = 1; begin <= end; begin++) {
                if (arr[begin] < arr[begin - 1]) {
                    swap(arr, begin - 1, begin);
                }
            }
        }
    }

    private void swap(int[] arr, int left, int right) {
        int temp = arr[right];        // 元素交换
        arr[right] = arr[left];
        arr[left] = temp;
    }

    public void sort01(int[] arr) {
        int len = arr.length;
        boolean sorted;

        if (len == 0)
            return;

        //  循环n次
        for (int end = len - 1; end > 0; end--) {
            sorted = true;
            for (int begin = 1; begin <= end; begin++) {
                if (arr[begin] < arr[begin - 1]) {
                    swap(arr, begin - 1, begin);
                    sorted = false;
                }
            }
            if (sorted) {
                break;
            }
        }
    }

    // 记录最后一次交换的地方
    public void sort02(int[] arr) {
        int len = arr.length;
        boolean sorted;
        int sortedIndex;

        if (len == 0)
            return;

        //  循环n次
        for (int end = len - 1; end > 0; end--) {
            sortedIndex = 0;
            sorted = true;
            for (int begin = 1; begin <= end; begin++) {
                if (arr[begin] < arr[begin - 1]) {
                    swap(arr, begin - 1, begin);
                    sorted = false;
                    sortedIndex = begin;
                }
            }
            if (sorted) {
                break;
            }
            end = sortedIndex;
        }
    }
}


class SelectionSort {

    public void sort(int[] arr) {
        int len = arr.length;
        if (len <= 1) {
            return;
        }
        int maxIndex;


        for (int end = len - 1; end > 0; end--) {
            maxIndex = 0;
            for (int begin = 1; begin <= end; begin++) {
                if (arr[maxIndex] < arr[begin]) {
                    maxIndex = begin;
                }
            }
            swap(arr, maxIndex, end);
        }
    }

    private void swap(int[] arr, int left, int right) {
        int temp = arr[right];        // 元素交换
        arr[right] = arr[left];
        arr[left] = temp;
    }

    public void sort1(int[] arr) {
        int len = arr.length;
        if (len <= 1) {
            return;
        }


        int left = 0;
        int right = len - 1;
        while (left < right) {
            int max = left;  //记录无序区最大元素下标
            int min = left;  //记录无序区最小元素下标
            int j = 0;
            for (j = left + 1; j <= right; j++) {
                //找最大元素下标
                if (arr[j] < arr[min]) {
                    min = j;
                }
                //找最小元素下标
                if (arr[j] > arr[max]) {
                    max = j;
                }
            }
            //最小值如果是第一个则没有必要交换
            if (min != left) {
                int tmp = arr[left];
                arr[left] = arr[min];
                arr[min] = tmp;
            }
            //这里很重要，如果最大元素下标是left,前面已经和最小元素交换了，此时最大元素下标应该是min
            if (max == left) {
                max = min;
            }
            //最大值如果是最后一个则没必要交换
            if (max != right) {
                int tmp = arr[right];
                arr[right] = arr[max];
                arr[max] = tmp;
            }
            left++;
            right--;
        }
    }

}


class QuickSort {

    public void sort(int[] arr, int begin, int end) {

        if (end - begin < 1) {
            return;
        }

        // 确定轴点位置
        int mid = pivotIndex(arr, begin, end);
        System.out.println("-------------分割线------------------");
        System.out.println("本次开始位置：" + begin);
        System.out.println("本次结束位置：" + end);
        System.out.println("本次轴元素位置：" + mid);
        System.out.println("本次轴元素数值：" + arr[mid]);
        System.out.println("本次数组：" + Arrays.toString(arr));
        // 对子序列进行快速排序
        sort(arr, begin, mid - 1);
        sort(arr, mid + 1, end);
    }

    // 构造出[begin,end]范围的轴点元素
    public int pivotIndex(int[] arr, int begin, int end) {
        int pivot = arr[begin];      //arr[begin]即arr[begin]就是第一个坑

        while (begin < end) {
            // 从右向左找小于x的数来填arr[begin]
            while (begin < end && arr[end] > pivot) {
                end--;
            }


            if (begin < end) {
                arr[begin] = arr[end]; //将arr[end]填到arr[begin]中，arr[end]就形成了一个新的坑
                begin++;
            }

            // 从左向右找大于或等于x的数来填arr[end]
            while (begin < end && arr[begin] < pivot) {
                begin++;
            }

            if (begin < end) {
                //将arr[begin]填到arr[end]中，arr[begin]就形成了一个新的坑
                arr[end] = arr[begin];
                end--;
            }
        }
        //退出时，begin等于end。将pivot填到这个坑中。
        arr[begin] = pivot;
        return begin;
    }


}

// 插入排序
class InsertSort {

    public void sort(int[] arr, int begin, int end) {

        if (end - begin < 1) {
            return;
        }

        // 确定轴点位置
        int mid = pivotIndex(arr, begin, end);
        System.out.println("-------------分割线------------------");
        System.out.println("本次开始位置：" + begin);
        System.out.println("本次结束位置：" + end);
        System.out.println("本次轴元素位置：" + mid);
        System.out.println("本次轴元素数值：" + arr[mid]);
        System.out.println("本次数组：" + Arrays.toString(arr));
        // 对子序列进行快速排序
        sort(arr, begin, mid - 1);
        sort(arr, mid + 1, end);
    }

    // 构造出[begin,end]范围的轴点元素
    public int pivotIndex(int[] arr, int begin, int end) {
        int pivot = arr[begin];      //arr[begin]即arr[begin]就是第一个坑

        while (begin < end) {
            // 从右向左找小于x的数来填arr[begin]
            while (begin < end && arr[end] > pivot) {
                end--;
            }


            if (begin < end) {
                arr[begin] = arr[end]; //将arr[end]填到arr[begin]中，arr[end]就形成了一个新的坑
                begin++;
            }

            // 从左向右找大于或等于x的数来填arr[end]
            while (begin < end && arr[begin] < pivot) {
                begin++;
            }

            if (begin < end) {
                //将arr[begin]填到arr[end]中，arr[begin]就形成了一个新的坑
                arr[end] = arr[begin];
                end--;
            }
        }
        //退出时，begin等于end。将pivot填到这个坑中。
        arr[begin] = pivot;
        return begin;
    }


}


//
//public class QuickSort3Ways {
//
//    // 递归使用快速排序,对arr[l...r]的范围进行排序
//    private static void sort(Comparable[] arr, int l, int r){
//
//        // 对于小规模数组, 使用插入排序
//        if( r - l <= 15 ){
//            InsertionSort.sort(arr, l, r);
//            return;
//        }
//
//        // 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot
//        swap( arr, l, (int)(Math.random()*(r-l+1)) + l );
//
//        Comparable v = arr[l];
//
//        int lt = l;     // arr[l+1...lt] < v
//        int gt = r + 1; // arr[gt...r] > v
//        int i = l+1;    // arr[lt+1...i) == v
//        while( i < gt ){
//            if( arr[i].compareTo(v) < 0 ){
//                swap( arr, i, lt+1);
//                i ++;
//                lt ++;
//            } else if( arr[i].compareTo(v) > 0 ){
//                swap( arr, i, gt-1);
//                gt --;
//            } else{ // arr[i] == v
//                i ++;
//            }
//        }
//
//        swap( arr, l, lt );
//
//        sort(arr, l, lt-1);
//        sort(arr, gt, r);
//    }
//
//    public static void sort(Comparable[] arr){
//
//        int n = arr.length;
//        sort(arr, 0, n-1);
//    }
//
//    private static void swap(Object[] arr, int i, int j) {
//        Object t = arr[i];
//        arr[i] = arr[j];
//        arr[j] = t;
//    }
//
//}